import math

class Solution:
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        l = len(nums)
        if (l == 0) or (target < nums[0]):
            return 0

        low = 0
        high = l - 1
        mid = math.floor((low + high) / 2)

        while low <= high:
            if target == nums[mid]:
                return mid
            elif target < nums[mid]:
                high = mid - 1
            else:
                low = mid + 1

            mid = math.floor((low + high) / 2)        

        return mid + 1

s = Solution()
print(s.searchInsert([1,3], 2))
print(s.searchInsert([1,3,5,6], 5))
print(s.searchInsert([1,3,5,6], 2))
print(s.searchInsert([1,3,5,6], 7))
print(s.searchInsert([1,3,5,6], 0))


